package arithmetic.demo11;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 题目： 贪心_坏了的计算器
 */
class Solution {
    public int brokenCalc(int startValue, int target) {
        // 正难则反
        int bgein = target , end = startValue;
        // 记录返回结果
        int ret = 0;
        while(bgein != end) {
            // 大小判断
            if(bgein <= end) {
                // 接上++的个数
                ret += end - bgein;
                bgein = end;
            } else {
                // 奇偶判断
                if(bgein % 2 == 0) {
                    bgein /= 2;
                } else {
                    bgein++;
                }
                // 操作次数加+ 1 
                ret++; 
            }
        }

        return ret;
    }


}

/**
 * 贪心: 排序+贪心_合并区间
 */

class Solution1 {
    public int[][] merge(int[][] tar) {
        // 获取长度
        int length = tar.length;

        // 排序
        Arrays.sort(tar,(int[] a, int[] b)->{
            return a[0] - b[0];
        });

        List<int[]> ret = new ArrayList<>();
        // 初始化
        // 添加第一个元素
        ret.add(new int[]{tar[0][0], tar[0][1]});

        for(int i = 1; i < length ; i++) {
            // 获取左右区间
            int sz = ret.size();
            // 当前的区间
            int[]tmp = ret.get(sz-1);
            int left = tmp[0], right = tmp[1];
            // 下一个区间
            int leftN = tar[i][0], rightN = tar[i][1];

            if(right >= leftN) {

                // 进行合并
                ret.set(sz-1,new int[]{left,Math.max(rightN,right)});
            } else{
                // 否则添加
                ret.add( new int[]{leftN, rightN});
            }
        }

        // 最终返回
        return ret.toArray(new int[ret.size()][2]);
    }
}


/**
 * 贪心_并集+排序+贪心_无重叠区间
 */

class Solution2 {
    public int eraseOverlapIntervals(int[][] arr) {
        // 左区间排序
        Arrays.sort(arr, (a,b)->{
            return a[0]-b[0];
        });

        // 初始化
        int ret = 0, left = arr[0][0], right = arr[0][1];
        for(int i = 1; i < arr.length;i++) {
            // 得到下一个边界
            int leftN = arr[i][0], rightN = arr[i][1];
            // 判断是否相交
            if(right > leftN) {
                // 更新右边界的最小
                right = Math.min(right , rightN);
                ret++;
            } else {
                // 没有的话就全部更新
                left = leftN;
                right = rightN;
            }
        }

        return ret;
    }
}

/**
 * 贪心_并集+排序+贪心_最长数对列
 */
class Solution3 {
    public int findLongestChain(int[][] pairs) {
        // 贪心做法
        // 左边界排序
        Arrays.sort(pairs, (a,b)->{
            return a[0] - b[0];
        });

        // 初始化
        int ret = 1, left = pairs[0][0], right = pairs[0][1];

        for(int i = 1; i < pairs.length; i++) {
            int leftN = pairs[i][0], rightN = pairs[i][1];
            if(right >= leftN) {
                // 更新右边界为最小
                right = Math.min(right, rightN);
            } else {
                ret++;
                // 不能合并
                left = leftN;
                right = rightN;
            }
        }

        return ret;
    }
}


/**
 * 动态规划_最长递增子序列思路_最长数对链
 */

class Solution4 {
    public int findLongestChain(int[][] pairs) {
        // 动态规划策略
        int length = pairs.length;

        // 排序
        Arrays.sort(pairs, (a,b)->{
            return a[0]- b[0];
        });

        // 创建dp
        int[] dp = new int[length];

        // 初始化
        Arrays.fill(dp,1);

        for(int i = 1; i < length; i++) {
            for(int j = 0; j < i ; j++) {
                // 符合递增长度
                if(pairs[i][0] > pairs[j][1]) {
                    // 更新长度
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }

        int ret = 0;
        for(int i = 0; i < length; i++) {
            ret = Math.max(ret, dp[i]);
        }

        return ret;
    }
}